package com.dq.offer;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/9  19:45
 * @Description: 剑指 Offer 14- I. 剪绳子
 */
public class CutTheRope {
    public static void main(String[] args) {
        Solution solution = new CutTheRope().new Solution();
        System.out.println(solution.cuttingRope(8));
        StringBuilder s = new StringBuilder();

    }
    class Solution {
        public int cuttingRope(int n) {
            if(n<2) return 0;
            if(n==2) return 1;
            if(n==3) return 2;

            int yu = n % 3 ;
            if(yu == 2) return (int)Math.pow(3, n/3) * 2;
            return (int)Math.pow(3, n/3 - 1) * 4;
        }
        public int cuttingRope2(int n) {
            int[] dp = new int[n+1];
            Arrays.fill(dp, 0);
            int ans = dp[0] = dp[1] = 1;
            for(int i = 2; i <= n ; i++){

                for(int j = 1; j < i; j++){
                    int t1 = (j > dp[j]?j:dp[j]) * ((i-j) > dp[i-j]?(i-j):dp[i-j]);

                    dp[i] = t1 > dp[i]? t1:dp[i];
                }
            }
            System.out.println(Arrays.toString(dp));
            return dp[n];

        }
    }
}
